package main

import "fmt"

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type ListNode struct {
	Val  int
	Next *ListNode
}

func createLine(valList []int) *ListNode {
	head := &ListNode{}
	cur := head
	for _, val := range valList {
		cur.Next = &ListNode{Val: val}
		cur = cur.Next
	}
	return head.Next
}

func printLine(head *ListNode) {
	for head != nil {
		fmt.Print(head.Val, " ")
		head = head.Next
	}
	fmt.Println()
}

func reverseBetween(head *ListNode, left int, right int) *ListNode {
	// 设置 dummyNode 是这一类问题的一般做法
	//dummyNode := &ListNode{Val: -1}
	//dummyNode.Next = head
	//pre := dummyNode
	//for i := 0; i < left-1; i++ {
	//	pre = pre.Next
	//}
	//cur := pre.Next
	//for i := 0; i < right-left; i++ {
	//	next := cur.Next
	//	cur.Next = next.Next
	//	next.Next = pre.Next
	//	pre.Next = next
	//}
	//return dummyNode.Next
	headNew := &ListNode{Next: head}
	pre := headNew
	for i := 0; i < left-1; i++ {
		pre = pre.Next
	}
	nodeLeft := pre.Next
	for i := 0; i < right-left; i++ {
		nodeNext := nodeLeft.Next
		nodeLeft.Next = nodeNext.Next
		nodeNext.Next = pre.Next
		pre.Next = nodeNext
	}
	return headNew.Next
}

func main() {
	printLine(reverseBetween(createLine([]int{1, 2, 3, 4, 5}), 2, 4))
}
